这道题不就是我在 Unique Paths 里面提到的最短路径问题嘛。不过其实解法和那道题类似，我们还是采取划分子问题的方式来分析：
可以看到，在最后一步的选择中，要么选择从上面下来，要么选择从左边过来，很显然，选择小的那个。那么 DP 公式呼之欲出：
f[i][j] = min(f[i-1][j], [i][j-1]) + grid[i][j];于是咱们就可以采取和上一道题同样的方式，用DP的思路来进行迭代了。（迭代过程中记录每一步的解）
比那道题要好的一点在于，这次给的是一个 vector，而且采用的是 reference 的方式，很显然，我们根本不需要额外使用空间，只需要将时间复杂度尽量降低即可。
我绘制了一幅图，可以理顺整个流程：
有几个特殊情况要考虑：
- 对于第一格，跳过，因为必选。
- 对于第一行，f[i][j] = grid[i][j] + grid[i][j-1]
- 对于第一列，f[i][j] = grid[i][j] + grid[i-1][j]
- 其余情况下，f[i][j] = min(grid[i][j-1], grid[i-1][j]) + grid[i][j]
然后，几乎代码呼之欲出了。。。
#include <algorithm>
#include <vector>
using std::vector;
class Solution {
public:
int minPathSum(vector<vector<int> > &grid) {
for (decltype(grid.size()) i=0; i<grid.size(); ++i)
for (decltype(grid[0].size()) j=0; j<grid[0].size(); ++j)
if (i == 0 && j == 0) continue;
else if (i == 0) grid[i][j] += grid[i][j-1];
else if (j == 0) grid[i][j] += grid[i-1][j];
else grid[i][j] += std::min(grid[i-1][j], grid[i][j-1]);
return grid.back().back();
}
};